import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-09-29
 * Time: 22:29
 */
class BTNode{
    public char val;
    public BTNode left;
    public BTNode right;
    public BTNode(char val){
        this.val=val;
    }
}
public class BinaryTree {
    public BTNode root;
    public BTNode creatTree(){
        BTNode A=new BTNode('A');
        BTNode B=new BTNode('B');
        BTNode C=new BTNode('C');
        BTNode D=new BTNode('D');
        BTNode E=new BTNode('E');
        BTNode F=new BTNode('F');
        BTNode G=new BTNode('G');
        BTNode H=new BTNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        //D.right=H;
        return A;
    }

    /**
     * 得到节点的个数
     * @param root
     * @return
     */
    public int size(BTNode root){
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }

    /**
     * 得到叶子节点的个数
     * @param root
     * @return
     */
    public int getLeafCount(BTNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafCount(root.left)+getLeafCount(root.right);
    }

    /**
     * 得到第K层节点个数
     * @return
     */
    public  int getKSize(BTNode root,int k){
        if(root==null||k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKSize(root.left,k-1)+getKSize(root.right,k-1);
    }

    /**
     * 检测值为value的节点是否存在
     */
    public BTNode isExist(BTNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }

        BTNode node=isExist(root.left,val);
        if(node!=null){
            return node;
        }
        return isExist(root.right,val);
    }

    /**
     * 判断一棵树是不是完全二叉树
     * 利用队列层序遍历的方法判断
     * @param root
     */
    public boolean isCompleteTree(BTNode root){
        Queue<BTNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            BTNode parent=queue.poll();
            if(parent!=null){
                queue.offer(parent.left);
                queue.offer(parent.right);
            }else {
                break;
            }
        }
        return isAllNull(queue);
    }

    private boolean isAllNull(Queue<BTNode> queue){
        int size=queue.size();
        for (int i = 0; i < size; i++) {
            if(queue.poll()!=null){
                return false;
            }
        }
        return true;
    }

}
